package com.gupao.alg.alg100;

import java.util.Arrays;

/**
 * 斐波那契数列
 */
public class FibonacciTest {
    public static int count = 0;
    public static int[] arr = new int[100];

    public static void main(String[] args) {
        Arrays.fill(arr, -1);
        int testMethod = 2;
        int result = -1, n = 20;
        switch (testMethod) {
            case 1://方法1：普通的递归
                count=0;
                result = Fibonacci(n);
                break;
            case 2://方法2：使用数组缓存已经计算完的
                count=0;
                result = FibonacciWithArary(n);
                break;
            case 3://方法3：不使用递归
                count=0;
                result = FibonacciSimpleAdd(n);
                break;
        }
        System.out.println(result);

        System.out.println("count:" + count);

    }

    /**
     * 方法1：普通的递归
     * @param n
     * @return
     */
    public static int Fibonacci(int n) {
        System.out.println("我爱你");
        count++;
        if (n == 0 || n == 1)
            return n;
        else {
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }

    /**
     * 方法2：使用数组缓存已经计算完的
     * @param n
     * @return
     */
    public static int FibonacciWithArary(int n) {
        System.out.println("我爱你");
        count++;
        if (n <= 2) {
            return n;
        }
        //先判断有没计算过
        if (arr[n] != -1) {
            //计算过，直接返回
            return arr[n];
        } else {
            // 没有计算过，递归计算,并且把结果保存到 arr数组里
            arr[n] = FibonacciWithArary(n - 1) + FibonacciWithArary(n - 2);
            return arr[n];
        }
    }

    /**
     * 方法3：不使用递归
     * @param n
     * @return
     */
    public static int FibonacciSimpleAdd(int n) {

        if (n <= 2)
            return n;
        int f1 = 1;
        int f2 = 2;
        int sum = 0;
        for (int i = 3; i <= n; i++) {
            sum = f1 + f2;
            f1 = f2;
            f2 = sum;
        }
        return sum;
    }
}
